#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int cuttingRope(int n) {
        if(n==1)return 1;
        if(n==2)return 1;
        if(n==3)return 2;

        //定义容器
        vector<int> dp(n+1, 0);

        //初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;

        for (int i = 4; i <= n ; i++)
        {
            int maxValue = 0;
            for (int j = 0; j <= i/2; j++)
            {
                maxValue = max(maxValue, dp[j]*dp[i-j]);
            }
            dp[i] = maxValue;
        }
    return dp[n];
    }
};